// 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

// 两棵树重复是指它们具有相同的结构以及相同的结点值。

// 示例 1：

//         1
//        / \
//       2   3
//      /   / \
//     4   2   4
//        /
//       4
// 下面是两个重复的子树：

//       2
//      /
//     4
// 和

//     4
// 因此，你需要以列表的形式返回上述重复子树的根结点。

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/* 深度优先搜索 + 序列化
时间复杂度：O(n^2)
空间复杂度：O(n^2)
*/
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> hash{};
        vector<TreeNode*> res{};
        func(root, hash, res);
        return res;
    }
    string func(TreeNode* node, unordered_map<string, int>& hash, vector<TreeNode*>& res) {
        if (node == nullptr) return "#";
        string serial = to_string(node->val) + "," + func(node->left, hash, res) + "," + func(node->right, hash, res);
        ++hash[serial];
        if (hash[serial] == 2) {
            res.push_back(node);
        }
        return serial;
    }
};

/* 唯一标识符
假设每棵子树都有一个唯一标识符：只有当两个子树的 id 相同时，认为这两个子树是相同的。
一个节点 node 的左孩子 id 为 x，右孩子 id 为 y，那么该节点的 id 为 (node.val, x, y)。
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        t = 1;
        lookup(root);
        return res;
    }
    int lookup(TreeNode* node) {
        if (node == nullptr) return 0;
        string serial = to_string(node->val) + "," + to_string(lookup(node->left)) + "," + to_string(lookup(node->right));
        int uid = trees[serial];
        ++count[uid];
        if (count[uid] == 2) {
            res.push_back(node);
        }
        return uid;
    }
private:
    int t{0};
    unordered_map<string, int> trees{};
    unordered_map<int, int> count{};
    vector<TreeNode*> res{};
};